import java.util.*;

public class Solution1 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> check = new HashSet<>();
        Set<String> hash = new HashSet<>();
        for(String s : wordList) {
            hash.add(s);
        }
        if(beginWord.equals(endWord)) {
            return 0;
        }
        if(!hash.contains(endWord)) {
            return 0;
        }
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        check.add(beginWord);
        int step = 0;

        while(!q.isEmpty()) {
            step++;
            int sz = q.size();
            for(int i = 0; i < sz; i++) {
                String t = q.poll();
                for(int j = 0; j < t.length(); j++) {
                    char[] tmp = t.toCharArray();
                    for(int k = 0; k < 26; k++) {
                        tmp[j] = (char)('a' + k);
                        String str = new String(tmp);
                        if(hash.contains(str) && !check.contains(str)) {
                            q.add(str);
                            check.add(str);
                            if(str.equals(endWord)) {
                                step++;
                                return step;
                            }
                        }
                    }
                }
            }
        }
        return 0;
    }
}
